Suppose one is given a $d$-dimensional subspace, represented as the column span of an $n \times d$ matrix $A$ with $O(\log(nd))$-bit entries, and would like to compress it in an arbitrary way to build a data structure $Q_p$, so that simultaneously for every query $x \in \mathbb{R}^d$, one has $Q_p(x) = (1 \pm \epsilon) \|Ax\|_p$. How many bits are required to store $Q_p$? For $p = 2$, one can store $A^TA$ using $O(d^2\log(nd))$ bits, independent of $\epsilon$, so that given a query $x$, one can output $x^T (A^TA) x = \|Ax\|_2^2$. However, for $p = 1$, the size of the smallest data structure known is $\widetilde{O}(\epsilon^{-2} d^2)$, where the $\widetilde{O}$ suppresses $\log(nd \epsilon^{-1})$ factors. Is the dependence on $\epsilon$ necessary?

We show if $p \geq 1$ is a real number that is {\em not an even integer} and $d = \Omega(\log(1/\epsilon))$, then $\widetilde{\Omega}(\epsilon^{-2} \cdot d)$ bits are required. Our result has a number of implications for geometric functional analysis. Our techniques, based on communication complexity, also give alternative proofs of known results in functional analysis, such as the $d^{p/2}$ dimension lower bound for embedding $d$-dimensional subspaces of $L_p$ into $\ell_p$.